# source: https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-i/ 滑动窗口 
class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        count = Counter(word2)
        i, ans = 0, 0
        d = defaultdict(int)
        for j, v in enumerate(word1):
            d[v] += 1
            while all(d[key] >= count[key] for key in count.keys()):
                ans += len(word1) - j
                d[word1[i]] -= 1
                i += 1
        return ans  
    
# source：https://leetcode-cn.com/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii/ 滑动窗口 O(26n) -> O(n)
class Solution:
    def validSubstringCount(self, s: str, t: str) -> int:
        if len(s) < len(t):
            return 0

        # t 的字母出现次数与 s 的字母出现次数之差
        diff = defaultdict(int)  # 也可以用 Counter(t)，但是会慢很多
        for c in t:
            diff[c] += 1

        # 窗口内有 less 个字母的出现次数比 t 的少
        less = len(diff)

        ans = left = 0
        for c in s:
            diff[c] -= 1
            if diff[c] == 0:
                # c 移入窗口后，窗口内 c 的出现次数和 t 的一样
                less -= 1
            while less == 0:  # 窗口符合要求
                if diff[s[left]] == 0:
                    # s[left] 移出窗口之前，检查出现次数，
                    # 如果窗口内 s[left] 的出现次数和 t 的一样，
                    # 那么 s[left] 移出窗口后，窗口内 s[left] 的出现次数比 t 的少
                    less += 1
                diff[s[left]] += 1
                left += 1
            ans += left
        return ans

# source:https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/  滑动窗口 同上 ans += left
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        d = defaultdict(int)
        i, ans = 0, 0
        n = len(nums)
        mx = max(nums)
        for j, v in enumerate(nums):
            d[v] += 1
            while d[mx] >= k:
                d[nums[i]] -= 1
                i += 1
            ans += i
        return ans

# source:https://leetcode.cn/problems/number-of-substrings-containing-all-three-characters/ 滑动窗口
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        d = defaultdict(int)
        i, ans = 0, 0
        for j, v in enumerate(s):
            d[v] += 1
            while all(d[k] >= 1 for k in ['a', 'b', 'c']):
                d[s[i]] -= 1
                i += 1
            ans += i
        return ans

# 法二：
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        d = defaultdict(int)
        i, ans = 0, 0
        count = {'a':1, 'b':1, 'c':1}
        less = len(count)
        for j, v in enumerate(s):
            count[v] -= 1
            if count[v] == 0:
                less -= 1
            while less == 0:
                count[s[i]] += 1
                if count[s[i]] == 1:
                    less += 1
                i += 1
            ans += i
        return ans